package code.starivan.leetcode;

/**
 * Created by Ivan on 2015/10/21.
 */

/*
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

        For example,
        Given n = 3, there are a total of 5 unique BST's.

        1         3     3      2      1
        \       /     /      / \      \
        3     2     1      1   3      2
        /     /       \                 \
        2     1         2                 3

*/

public class N096_UniqueBinarySearchTrees {
    public static void test(){
        System.out.println(new N096_UniqueBinarySearchTrees().numTrees(3));
    }

    public int numTrees(int n) {
        if(n<=0){
            return 0;
        }

        int[] help=new int[n+1];
        help[0]=1;
        help[1]=1;

        for(int i=2;i<=n;++i){
            int count=0;
            for(int j=1;j<=i;++j){
                count+=help[j-1]*help[i-j];
            }

            help[i]=count;
        }

        return help[n];
    }
}
